// #include"AVLtree.h"
#include<set>

#if 0

struct my_cmp
{
	// 按绝对值大小比较
	bool operator()(int a, int b) const
	{
		return abs(a) < abs(b);
	}
};
void test_avl()
{
    // AVLtree<int> t = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    // AVLtree<int>::const_iterator it = t.begin();    // 隐式类型转化
    // while(it != t.end())
    // {
    //     cout << *it << ' ';
    //     ++it;
    // }

    // AVLtree<int, my_cmp> t1 = {-16, -3, 7, 11, -9, 26, -18, 14, -15};
    // for(auto it = t1.begin(); it != t1.end(); ++it)
    // {
    //     // *it = 10; // 可以修改
    //     cout << *it << ' ';
    // }

    const AVLtree<int, my_cmp> t1 = {-16, -3, 7, 11, -9, 26, -18, 14, -15};
    for(auto it = t1.begin(); it != t1.end(); ++it)
    {
        // *it = 10; // err 不可修改
        cout << *it << ' ';
    }
}

#include<set>

void test_set01()
{
    // set是有序容器，会按一定顺序存储元素，默认是升序。底层一般用红黑树实现

    set<int> s; // 默认构造

    int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    set<int> s1(a, a + 5); // 迭代器区间构造，用a数组的[0, 5)构造

    set<int> s2(s1); // 拷贝构造
    // 迭代器遍历
    auto it2 = s2.begin();
    while(it2 != s2.end())
    {
        cout << *it2 << ' ';
        // *it2 = 1; // err 注意set容器内的元素不可以修改
        ++it2;
    }

    cout << s2.size() << endl; // 返回s2中的元素个数
    cout << s2.empty() << endl;// 为空返回true，否则返回false

    auto p = s2.insert(999); // 插入999。注意set不支持插入重复数据，若容器中已有999，则插入失败
    // 返回值是pair<iterator, bool>
    // 成功插入返回 <该元素的迭代器, true>, 否则返回 <该元素的迭代器, false>
    cout << *(p.first) << ' ' << p.second << endl;  // 输出 999 1

    int cnt = s2.erase(3);  // 删除3
    // 返回成功删除的元素个数。对与set而言：成功删除返回1，否则返回0

    it2 = s2.find(16); // 查找16，容器中存在16则返回指向16的迭代器，否则返回end()
    cnt = s2.count(26);     // 返回值为26的元素个数。对与set而言：容器中存在26返回1，否则返回0

    s2.insert(5);
    it2 = s2.lower_bound(5);    // 返回容器中 >= 5的最小元素的迭代器
    it2 = s2.upper_bound(5);    // 返回容器中 > 5的最小元素的迭代器

    s2.clear();     // 清空容器
    s2.swap(s1);    // 与s1交换

    // set的查找、插入、删除、lower_bound、upper_bound 时间复杂度都是log(N)
}

#include<map>
void test_map01()
{
    // set存储的是单个元素，而map存储的数据是键值对：{key, value}，按key从小到大的顺序
    map<string, int> m; // 默认构造，
    // m存储的数据类型是 pair<string, int>, 更严格来说是pair<const string, int>，键不可修改

    m.insert({"小明", 15});     // 插入，数据类型是pair<string,int>("小明", 15)
    m.insert({"小明", 999});    // 注意：如果key已经在容器中存在，则插入失败
    m.insert({"小红", 16});
    auto p = m.insert({"小张", 18});
    // map的insert与set类似，返回pair<iterator, bool>
    // 成功插入返回 <该键值对的迭代器, true>, 否则返回 <该键值对的迭代器, false>

    cout << p.first->first << ' ' << p.first->second << ' ' << p.second << endl;
    // p.first是指向键值对{key, value}的迭代器

    // 但是插入操作一般用operator[]
    // value& operator[](const key& k);
    // 参数是key，返回值是value的引用
    // 该函数会先调用insert({k, value()}); // value()是value的默认值
    // 插入后返回value

    int age = m["小红"]; // 若容器中已存在key为"小红"的数据，则返回其对应的value的引用

    m["张三"] = 20;     // 若容器中已存在key为"张三"的数据，将其修改为20，否则就相当于insert({"张三", 20});

    m.erase("小明");    
    // 将key为"小明"的数据, 返回值是成功删除的数据个数。对与map而言，容器中存在key为"小明"的数据返回1，否则返回0

    // 迭代器遍历
    auto it = m.begin();    // 返回第一个指向键值对的迭代器
    while(it != m.end())
    {
        cout << it->first << ' ' << it->second << endl; // first是键，second是值
        // it->first = "xxx";  // err 键不可修改
        it->second = 999;   // 值可以修改
        ++it;
    }

    it = m.find("小张"); // 查找 键为"小明"的数据，成功找到返回其迭代器，否则返回end()

    cout << m.size() << endl; // 返回m中的元素个数
    cout << m.empty() << endl;// 为空返回true，否则返回false

    int cnt = m.count("张三");     
    // 返回key为张三的数据个数。对与map而言：容器中存在key为"张三"的数据返回1，否则返回0

    m.clear(); // 清空容器
}
#endif

#include"set_map.h"
void test_my_set01()
{
    set<int> s;
    int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    
    pair<set<int>::iterator, bool> t;
    for(auto e : a) 
        t = s.insert(e);

    set<int>::iterator it;
    for(it = s.begin(); it != s.end(); ++it)
        cout << *it << ' ';
    
    cout << s.size() << endl;
    cout << s.empty() << endl;

    it = s.lower_bound(7);
    it = s.upper_bound(7);
    it = s.find(12);
    it = s.find(11);

    int cnt = s.count(12);
    cnt = s.count(11);

    cnt = s.erase(11);
    cnt = s.erase(14);
    cnt = s.erase(17);
    for(it = s.begin(); it != s.end(); ++it)
        cout << *it << ' ';
    cout << s.size() << endl;
    
}

struct my_cmp
{
	bool operator()(int a, int b) const
	{ return abs(a) < abs(b); }
};

void test_my_set02()
{
    set<int, my_cmp> s;
    int a[] = {-16, 3, 7, -11, 9, -26, 18, -14, 15};
    
    pair<set<int>::iterator, bool> t;
    for(auto e : a) 
        t = s.insert(e);

    set<int>::iterator it;
    for(it = s.begin(); it != s.end(); ++it)
        cout << *it << ' ';
    
    cout << s.size() << endl;
    cout << s.empty() << endl;

    it = s.lower_bound(-7);
    it = s.lower_bound(7);
    it = s.upper_bound(-7);
    it = s.upper_bound(7);
}
int main()
{
    // auto p = pair<string,int>("小明", 15);
    // // auto& p1 = pair<string,int>("小明", 15); // err

    // // auto& r = 2;    // err, auto不会推到为const int
	// const int a = 10;
	// const const int b = 10;
    test_my_set01();
    return 0;
}

// void test01()
// {
// 	set<int, my_cmp> st = {-16, 3, 7, -11, -9, 26, 18, -14, -15};
// 	for (int e : st)
// 		cout << e << ' ';
// 	cout << endl;
// 	set<int> st1 = {-16, 3, 7, -11, -9, 26, 18, -14, -15};
// 	for (int e : st1)
// 		cout << e << ' ';
// }

// void test02()
// {
//     map<string, string> d;
//     d["香蕉"];
//     d["香蕉"] = "banana";
//     d["苹果"] = "apple";
//     d["华为"] = "huawei";
//     auto it = d.begin();
//     while(it != d.end())
//     {
//         cout << it->first << ' ' << it->second << endl;
//         ++it;
//     }
// }

// void test_avl()
// {
//     AVLtree<int> t = {-16, 3, 7, -11, -9, 26, 18, -14, -15};
//     // auto it = t.begin();
//     // while(it != t.end())
//     // {
//     //     cout << *it << ' ';
//     //     ++it;
//     // }

//     auto it = --t.end();
//     while(it != t.begin())
//     {
//         cout << *it << ' ';
//         --it;
//     }
// }

// int main()
// {
//     test_avl();
//     return 0;
// }
